import java.util.Comparator;
import java.util.Objects;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-10-30
 * Time:9:43
 */
class Card{
    public String suit;
    public int rank;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Card card = (Card) o;
        return rank == card.rank && suit.equals(card.suit);
    }

    @Override
    public int hashCode() {
        return Objects.hash(suit, rank);
    }
}
class IntInt implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}
public class Test {
    int elem[];
    int useSize=0;
    public static final int DEFAULT_SIZE=10;

    public Test(int[] elem) {
        this.elem = new int[DEFAULT_SIZE];
    }

    //创建
    public void create(int[]arr){
        for (int i = 0; i < arr.length; i++) {
            elem[i]=arr[i];
            useSize++;
        }
        int parent=(arr.length-1)/2;
        while(parent>=0){
            shiftDownBig(parent,useSize);
            parent--;
        }

    }

    //大根堆
    //向下调整
    public void shiftDownBig(int parent,int len){
        int child=parent*2+1;
        while(child<len){
            //判断孩子哪个大
            if (elem[child] < elem[child+1]&&child+1<len) {
                child =child+1;
            }
            if(elem[child]>elem[parent]){
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                parent=child;
                child=parent*2+1;
            }else {
                break;
            }
        }
    }
    //小根堆
    public void shiftDownSmall(int parent,int len){
        int child=parent*2+1;
        while(child<len){
            //判断孩子哪个小
            if (elem[child] > elem[child+1]&&child+1<len) {
                child =child+1;
            }
            if(elem[child]<elem[parent]){
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                parent=child;
                child=parent*2+1;
            }else {
                break;
            }
        }
    }
    //利用堆进行排序
    //从小到大排序的话。用大根堆，小根堆排序，只能找到最小的值，但是不能保证里面的树是排好序的
    public void sort(){
        if(elem==null){
            return;
        }
        int end=elem.length-1;
        while(end>=0){
            //是大根堆
            int tmp=elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            end--;
            shiftDownBig(0,end);
        }
    }
    //插入排序
    //直接插入排序
    //时间复杂度：O(n^2)~O(n)
    //当数据量不多，且趋于有序的直接插入排序是非常快的
    //空间复杂度：O(1)
    //稳定性：稳定
    //一个本身就稳定的排序，可以实现一个不稳定的排序。但是一个不稳定的排序不能实现一个稳定的排序
    public void insertSort(int []array){
        //每一次都需要调试
        for (int i = 0; i < array.length; i++) {
            int tmp=array[i];
            int j = i-1;
            //循环找前面的大小的元素
            for (; j >0; j--) {
                if(array[j]>tmp){
                    //换位置
                    array[j+1]=array[j];
                }else {
                    break;
                }
            }
            array[j+1]=tmp;
        }
        long begin=System.currentTimeMillis();
    }
    //希尔排序（插入排序的优化）
    //gap是一个跨度
}
